#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

using namespace std;

typedef struct TreeNode
{
	struct TreeNode* left;
	struct TreeNode* right;
	char val;
} TN;

TN* CreatTree(const string& s, int& i)
{
	if (s[i] == '#')
	{
		i++;
		return nullptr;
	}
	TN* root = new TN;
	root->val = s[i++];
	root->left = CreatTree(s, i);
	root->right = CreatTree(s, i);
	return root;
}

void PreOrder(TN* root)
{
	if (root == nullptr)
	{
		return;
	}
	cout << root->val << " ";
	PreOrder(root->left);
	PreOrder(root->right);
}

void InOrder(TN* root)
{
	if (root == nullptr)
	{
		return;
	}
	InOrder(root->left);
	cout << root->val << " ";
	InOrder(root->right);
}

void PostOrder(TN* root)
{
	if (root == nullptr)
	{
		return;
	}
	PostOrder(root->left);
	PostOrder(root->right);
	cout << root->val << " ";
}



void level_order(TN* root)
{

	TN* ch[1000];
	int left = 0;
	int right = 0;

	if (root)
	{
		ch[right++] = root;
	}


	while (left < right)
	{
		TN* tmp = ch[left++];
		cout << tmp->val << " ";
		if (tmp->left)
		{
			//q.push(tmp->left);
			ch[right++] = tmp->left;
		}
		if (tmp->right)
		{
			//q.push(tmp->right);
			ch[right++] = tmp->right;

		}
	}
	cout << endl;
	return;
}

void post_order_for_image_tree(TN*& root)
{
	if (root == nullptr)
	{
		return;
	}
	post_order_for_image_tree(root->left);
	post_order_for_image_tree(root->right);
	swap(root->left, root->right);
}

void image_Tree(TN*& root)
{
	if (root == nullptr)
	{
		int i = 4;
		while (i--)
		{
			cout << "NULL" << endl;
		}
		return;
	}
	post_order_for_image_tree(root);

	PreOrder(root);
	cout << endl;

	InOrder(root);
	cout << endl;

	PostOrder(root);
	cout << endl;

	level_order(root);
	
}

void test4()
{
	int t;
	cin >> t;
	while (t--)
	{
		string s;
		int i = 0;
		cin >> s;
		TN* root = CreatTree(s, i);

		image_Tree(root);
	}
}

int main()
{
	test4();
	return 0;
}